package com.leetcode.partition1;

/**
 * @author `RKC`
 * @date 2021/9/23 14:39
 */
public class LC91解码方法 {

    public static int numDecodings(String s) {
        return dynamicProgramming(s.toCharArray());
    }

    public static void main(String[] args) {
        String s = "10";
        System.out.println(numDecodings(s));
    }

    private static int dynamicProgramming(char[] messages) {
        if ((messages[0] - '0') == 0) return 0;
        //dp[i]：message[0, i]子串能正确解码的方案数
        int[] dp = new int[messages.length + 1];
        dp[0] = 1;
        for (int i = 1; i <= messages.length; i++) {
            //A-I只使用了一个字符，一个字符拼接上去还是以前的方案数
            if (messages[i - 1] != '0') dp[i] = dp[i - 1];
            //使用了两个字符，两个字符不能出现前导0
            if (i > 1 && messages[i - 2] != '0' && (messages[i - 2] - '0') * 10 + (messages[i - 1] - '0') <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[messages.length];
    }
}
